// 给定一个二叉树的根节点root，要求：返回其最大路径和
// 路径：从树中的任意节点出发，沿着父节点-子节点连接，到达任意子节点的序列，同一个节点在一条路径上最多出现一次，该路径至少包含一个节点，且不一定经过根节点
// 路径和：路径中各节点值的总和

// 思路，递归
// 维护一个最大路径和变量，经过当前节点的最大路径和等于 = 经过左子节点最大路径和 + 经过右子节点最大路径和 + 当前节点值
// 返回当前节点的最大贡献值 = 当前节点值 + Math.max(左子节点最大路径和 , 经过右子节点最大路径和)

function maxPathSum(root) {
    let maxSum = -Infinity
    function dfs(root) {
        if (!root) {
            return 0
        }
        let leftMax = Math.max(dfs(root.left), 0)
        let rightMax = Math.max(dfs(root.right), 0)
        maxSum = Math.max(maxSum, root.val + leftMax + rightMax)
        return root.val + Math.max(leftMax, rightMax)
    }
    dfs(root)
    return maxSum
}

const root = {
    val: 1,
    left: {
        val: 2,
        left: {
            val: 4,
        },
        right: {
            val: 5,
        },
    },
    right: {
        val: -6,
    },
};

console.log(maxPathSum(root));